package 单链表回文字符串;

public class jishengjun {

    public static void main(String[] args) {
        Node firstNode = getTestNode1();

        System.out.println(isPalindrome(firstNode));
    }

    public static boolean isPalindrome(Node firstNode) {
        Node currentNode = firstNode;
        if (firstNode == null || firstNode.isLast()) {
            return true;
        }
        Node preNode = null;
        while (currentNode != null) {
            if (currentNode.isLast()) {
                if (!firstNode.data.equals(currentNode.data)) {
                    return false;
                }
            }
            if (!currentNode.isLast()) {
                preNode = currentNode;
            }
            currentNode = currentNode.next;
        }
        preNode.next = null;
        firstNode = firstNode.next;
        return isPalindrome(firstNode);
    }


    private static Node getTestNode1() {
        //黄山落叶松叶落山黄
        Node node1 = new Node();
        node1.data = "黄";
        Node node2 = new Node();
        node2.data = "山";
        Node node3 = new Node();
        node3.data = "落";
        Node node4 = new Node();
        node4.data = "叶";
        Node node5 = new Node();
        node5.data = "松";
        Node node6 = new Node();
        node6.data = "叶";
        Node node7 = new Node();
        node7.data = "落";
        Node node8 = new Node();
        node8.data = "山";
        Node node9 = new Node();
        node9.data = "黄";

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        return node1;
    }

    static class Node {
        String data;
        Node next;

        boolean isLast() {
            return next == null;
        }

    }
}
